DEEP-FRING (DEEP-FRI over Rings)
Goal. Generalize FRI, Schwartz-Zippel and FFT to a commutative ring of the form $R = \mathbb Z/m \mathbb Z$ where $m = 2^b ⋅ k$ or something similar.
We want this to be able to construct a $2^{64}$ sub-ring that captures the behaviour of binary numbers without much fuzz.
We can tweak $k$ to guarantee the existence of roots of unity of order $2^r$, which will power FRI and FFT.
The ring $R$ is
Consequently, the ring of polynomials over it, $R[X]$ is
- Commutative
- Not integral
- Noetherian
Note. We need an integral domain in order to have the common rules on degree of the polynomial: https://en.wikipedia.org/wiki/Degree_of_a_polynomial#Behavior_under_polynomial_operations
To do. It does seem that this only reduces the degrees of the polynomials, and potentially only with neglible probability. So much of the theory can be salvaged. (i.e. $\deg (PQ) \leq (\deg P)(\deg Q)$).
Roots of unity
Schwartz-Zippel
https://mathoverflow.net/questions/186074/can-schwartz-zippel-be-formulated-for-commutative-rings-instead-of-fields
Unique factorization
For some theorems we need Polynomials to have a unique factorization into irreducible factors (i.e. in Plonk's multi-set check). This requires the field to be a unique factorization domain, but it isn't. In fact, it is not even an integral ring.
https://en.wikipedia.org/wiki/Unique_factorization_domain
https://en.wikipedia.org/wiki/Polynomial_ring#Factorization_in_K[X]
FFT+FRI
https://users.cs.duke.edu/~reif/courses/alglectures/reif.lectures/ALG3.2.pdf
FFT Seems to not be an issue as long as the roots of unity exist. FRI will follow the same path.
Reed-solomon over Rings
https://hal.inria.fr/hal-00670004v2/document
Commutative rings
A commutative ring is a set $\mathbb R$ with two binary operations $+$ and $⋅$ and two elements $0, 1 \in \mathbb R$ s.t.:
- Abelian group under addition.
- $+$ is closed $a + b \in \mathbb R$
- $+$ is commutative $a + b = b + a$
- $+$ is associative $(a + b) + c = a + (b + c)$
- $0$ is an additive identity $a + 0 = a$
- additive inverses $a + (-a) = 0$
- Monoid under multiplication
- $⋅$ is closed $a ⋅ b \in \mathbb R$
- $⋅$ is commutative $a ⋅ b = b ⋅ a$
- $⋅$ is associative $(a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)$
- $1$ is a multiplicative identity $a ⋅ 1 = a$
- Multiplication is distributive over addition
- distributivity
Q: Additive inverses unique? Q: Multiplicative inverses unique?
Definition. (Additive inverse). $-a$. By the axioms these always exist.
Definition. (Multiplicative inverse). $a^{-1}$. These do not necessarily exist.
Definition. (Unit). If $a$ has an inverse, it is called a unit.
Definition. (Zero divisor). If $a$ has an element $b$ such that $ab = 0$, it is called a zero divisor.
Definition. (Nilpotent). If $a$ has a positive number $n$ such that $a^n = 0$, it is called nilpotent.
Lemma. If $a$ is nilpotent then $1-a$ is a unit.
https://en.wikipedia.org/wiki/Root_of_unity_modulo_n
https://en.wikipedia.org/wiki/Root_of_unity_modulo_n#Finding_an_n_with_a_primitive_k-th_root_of_unity_modulo_n